/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package hoja.pkg3;
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
import java.util.ArrayList;
import java.util.List;
/**
 *
 * @author Mardiego
 */
public class Metodos {
    
    public Metodos()
    {
        
    }
    
    public List<Integer> insertionSort(List<Integer> lista)
    {
        for(int i=1; i<lista.size(); i++)
        {
            for(int j=0; j<i; j++)
            {
                if(lista.get(i)<lista.get(j))
                {
                    int temp=lista.get(i);
                    lista.add(j,temp);
                    lista.remove(i+1);
                    break;
                }
            }
        }
        return lista;
    }
    public List<Integer> selectionSort(List<Integer> lista) {
    for (int i=0; i<lista.size()-1; i++) {
        for (int j=i+1; j<lista.size(); j++) {
            if (lista.get(i) > lista.get(j)) {
                //... Exchange elements
                // codigo base tomado de http://www.leepoint.net/notes-java/data/arrays/32arraybubblesort.html
                int temp = lista.get(i);
                lista.set(i,lista.get(j));
                lista.set(j, temp);
            }
        }
    }
    return lista;
}
    public List <Integer> bubbleSort(List<Integer> lista) {
    int n = lista.size();
    boolean doMore = true;
    
    while (doMore) {
        n--;
        doMore = false;  // assume this is our last pass over the array 
        // el codigo base fue tomado de la misma pagina que el insertion sort
        for (int i=0; i<n; i++) {
            if (lista.get(i) > lista.get(i+1)) {
                // exchange elements
                int temp = lista.get(i); 
                lista.set(i,lista.get(i+1)); 
                lista.set(i+1, temp);
                doMore = true;  // after an exchange, must look again 
            }
            
        }
    }
    return lista;
}
    
      public List<Integer> quiksort(List<Integer> lista,int lo,int ho)
  {
    int t, l=lo, h=ho, mid;
 
    if(ho>lo)
    {
      mid=lista.get((lo+ho)/2);
      while(l<h)
      {
        while((l<ho)&&(lista.get(l)<mid))  ++l;
        while((h>lo)&&(lista.get(h)>mid))  --h;
        if(l<=h)
        {
          t = lista.get(l);
          lista.set(l,lista.get(h));
          lista.set(h,t);
          ++l;
          --h;
        }
      }
 
      if(lo<h) quiksort(lista,lo,h);
      if(l<ho) quiksort(lista,l,ho);
    }
    return lista;
  }

public int[] mergeSort(int array[],int lo, int n){
  int low = lo;
  int high = n;
  if (low >= high) {
  return array;
  }

  int middle = (low + high) / 2;
  mergeSort(array, low, middle);
  mergeSort(array, middle + 1, high);
  int end_low = middle;
  int start_high = middle + 1;
  while ((lo <= end_low) && (start_high <= high)) {
  if (array[low] < array[start_high]) {
  low++;
  } else {
  int Temp = array[start_high];
  for (int k = start_high- 1; k >= low; k--) {
  array[k+1] = array[k];
  }
  array[low] = Temp;
  low++;
  end_low++;
  start_high++;
  
  }
  }
  return array;
  }  

public int[] toarray(List<Integer> lista)
{
    int[] li=new int[lista.size()];
    for(int i=0; i<lista.size(); i++)
    {
        li[i]=lista.get(i);
    }
    return li; 
}
}
